#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
void InsertSort(int arr[], int sz)
{
	for (int i = 0; i < sz-1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end>=0)
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void ShellSort(int arr[], int sz)
{
	int gap = sz;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
			for (int i = 0; i < sz - gap; i++)
			{
				int end = i;
				int tmp = arr[end + gap];
				while (end >= 0)
				{
					if (arr[end] > tmp)
					{
						arr[end + gap] = arr[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				arr[end + gap] = tmp;
			}
	}
}
void SelectSort(int arr[], int sz)
{
	int begin = 0;
	int end = sz - 1;
	while (begin < end)
	{
		int maxi = begin, mini = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}
		if (begin == maxi)
		{
			maxi = mini;
		}
		Swap(&arr[begin], &arr[mini]);
		Swap(&arr[end], &arr[maxi]);
		begin++;
		end--;
	}
}
int QuickSort01(int arr[], int left, int right)
{
	int keyi = left;
	++left;
	while (left <= right)
	{
		while (left<=right && arr[right] > arr[keyi])
		{
			right--;
		}
		while (left<=right && arr[left] < arr[keyi])
		{
			left++;
		}
		if (left <= right)
		{
			Swap(&arr[left++], &arr[right--]);
		}
	}
	Swap(&arr[keyi], &arr[right]);
	return right;
}
void QuickSort(int arr[], int left,int right)
{
	if (left >= right)
	{
		return;
	}
	int keyi = QuickSort01(arr, left, right);
	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi + 1, right);
}
